<!DOCTYPE html>
<html lang="en-us" dir="ltr">
    <head><meta charset='utf-8'>
<meta name='viewport' content='width=device-width, initial-scale=1'><meta name='description' content="英特尔傲腾技术具有开创性地将内存和存储融为一体。持久内存是一项变革性的内存技术，持久内存将经济实惠的更大容量与对数据持久性的支持巧妙的结合在一起。以创新技术提供独特的操作模式，可以满足您针对各种工作负载的需求。">
<title>NVM方向调研</title>

<link rel='canonical' href='http://36.41.71.150/post/nvm_report/'>

<link rel="stylesheet" href="/scss/style.min.663803bebe609202d5b39d848f2d7c2dc8b598a2d879efa079fa88893d29c49c.css"><meta property='og:title' content="NVM方向调研">
<meta property='og:description' content="英特尔傲腾技术具有开创性地将内存和存储融为一体。持久内存是一项变革性的内存技术，持久内存将经济实惠的更大容量与对数据持久性的支持巧妙的结合在一起。以创新技术提供独特的操作模式，可以满足您针对各种工作负载的需求。">
<meta property='og:url' content='http://36.41.71.150/post/nvm_report/'>
<meta property='og:site_name' content='ydsungan 的博客'>
<meta property='og:type' content='article'><meta property='article:section' content='Post' /><meta property='article:published_time' content='2022-03-31T18:25:12&#43;08:00'/><meta property='article:modified_time' content='2022-03-31T18:25:12&#43;08:00'/><meta property='og:image' content='http://36.41.71.150/post/dcpmm.jpg' />
<meta name="twitter:title" content="NVM方向调研">
<meta name="twitter:description" content="英特尔傲腾技术具有开创性地将内存和存储融为一体。持久内存是一项变革性的内存技术，持久内存将经济实惠的更大容量与对数据持久性的支持巧妙的结合在一起。以创新技术提供独特的操作模式，可以满足您针对各种工作负载的需求。"><meta name="twitter:card" content="summary_large_image">
    <meta name="twitter:image" content='http://36.41.71.150/post/dcpmm.jpg' />
    </head>
    <body class="
    article-page
    ">
    <script>
        (function() {
            const colorSchemeKey = 'StackColorScheme';
            if(!localStorage.getItem(colorSchemeKey)){
                localStorage.setItem(colorSchemeKey, "auto");
            }
        })();
    </script><script>
    (function() {
        const colorSchemeKey = 'StackColorScheme';
        const colorSchemeItem = localStorage.getItem(colorSchemeKey);
        const supportDarkMode = window.matchMedia('(prefers-color-scheme: dark)').matches === true;

        if (colorSchemeItem == 'dark' || colorSchemeItem === 'auto' && supportDarkMode) {
            

            document.documentElement.dataset.scheme = 'dark';
        } else {
            document.documentElement.dataset.scheme = 'light';
        }
    })();
</script>
<div class="container main-container flex on-phone--column extended"><aside class="sidebar left-sidebar sticky ">
    <button class="hamburger hamburger--spin" type="button" id="toggle-menu" aria-label="Toggle Menu">
        <span class="hamburger-box">
            <span class="hamburger-inner"></span>
        </span>
    </button>

    <header>
        
            
            <figure class="site-avatar">
                <a href="/">
                
                    
                    
                    
                        
                        <img src="/img/avatar_hu10196295592476096514.jpg" width="300"
                            height="300" class="site-logo" loading="lazy" alt="Avatar">
                    
                
                </a>
                
                    <span class="emoji">🍥</span>
                
            </figure>
            
        
        
        <div class="site-meta">
            <h1 class="site-name"><a href="/">ydsungan 的博客</a></h1>
            <h2 class="site-description">任凭风浪起，稳坐钓鱼台</h2>
        </div>
    </header><ol class="menu-social">
            
                <li>
                    <a 
                        href='https://gitee.com/ydsungan'
                        target="_blank"
                        title="GitHub"
                        rel="me"
                    >
                        
                        
                            <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-brand-github" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z" fill="none"/>
  <path d="M9 19c-4.3 1.4 -4.3 -2.5 -6 -3m12 5v-3.5c0 -1 .1 -1.4 -.5 -2c2.8 -.3 5.5 -1.4 5.5 -6a4.6 4.6 0 0 0 -1.3 -3.2a4.2 4.2 0 0 0 -.1 -3.2s-1.1 -.3 -3.5 1.3a12.3 12.3 0 0 0 -6.2 0c-2.4 -1.6 -3.5 -1.3 -3.5 -1.3a4.2 4.2 0 0 0 -.1 3.2a4.6 4.6 0 0 0 -1.3 3.2c0 4.6 2.7 5.7 5.5 6c-.6 .6 -.6 1.2 -.5 2v3.5" />
</svg>



                        
                    </a>
                </li>
            
                <li>
                    <a 
                        href='https://twitter.com'
                        target="_blank"
                        title="Twitter"
                        rel="me"
                    >
                        
                        
                            <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-brand-twitter" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z" fill="none"/>
  <path d="M22 4.01c-1 .49 -1.98 .689 -3 .99c-1.121 -1.265 -2.783 -1.335 -4.38 -.737s-2.643 2.06 -2.62 3.737v1c-3.245 .083 -6.135 -1.395 -8 -4c0 0 -4.182 7.433 4 11c-1.872 1.247 -3.739 2.088 -6 2c3.308 1.803 6.913 2.423 10.034 1.517c3.58 -1.04 6.522 -3.723 7.651 -7.742a13.84 13.84 0 0 0 .497 -3.753c-.002 -.249 1.51 -2.772 1.818 -4.013z" />
</svg>



                        
                    </a>
                </li>
            
                <li>
                    <a 
                        href='https://weibo.com/u/7203149652'
                        target="_blank"
                        title="Weibo"
                        rel="me"
                    >
                        
                        
                            <?xml version="1.0" standalone="no"?><!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"><svg t="1728725633554" class="icon" viewBox="0 0 1024 1024" version="1.1" xmlns="http://www.w3.org/2000/svg" p-id="4295" xmlns:xlink="http://www.w3.org/1999/xlink" width="200" height="200"><path d="M507.722667 393.525333c3.018667-0.202667 5.685333-0.618667 7.594666-1.141333 15.626667-12.458667 47.68-28.864 76.8-37.802667 48-14.72 90.24-12.16 118.421334 18.688 8.490667 9.301333 14.346667 19.562667 17.386666 30.698667 6.314667 23.04 2.453333 37.184-11.754666 69.248-10.506667 23.722667-11.146667 29.888-3.808 39.530667 4.896 6.410667 10.432 8.917333 22.293333 10.24 3.157333 0.362667 5.749333 0.554667 12.373333 0.96 57.472 3.605333 84.970667 26.922667 84.970667 98.538666 0 86.901333-60.821333 158.005333-160.138667 208.64C592.554667 871.530667 491.818667 896 415.072 896c-90.773333 0-175.872-18.026667-237.312-59.882667C93.546667 778.752 63.68 683.445333 101.514667 553.536c30.154667-103.541333 158.357333-246.88 279.114666-298.4 27.082667-11.562667 61.685333-13.962667 86.709334-1.706667 38.378667 18.773333 44.693333 61.184 20.128 111.946667-9.525333 19.68-8.576 22.368-0.426667 25.525333 5.514667 2.133333 13.226667 3.104 20.682667 2.624z m-77.866667-56.021333c6.293333-13.013333 8.597333-22.101333 8.341333-27.018667-6.613333-2.368-21.568-1.130667-32.458666 3.52C302.528 358.026667 187.733333 486.4 162.965333 571.424c-30.368 104.245333-9.557333 170.656 50.826667 211.786667C262.56 816.448 335.978667 832 415.072 832c66.592 0 157.365333-22.048 227.722667-57.898667C722.944 733.248 768 680.565333 768 622.485333c0-12.224-1.12-21.141333-2.986667-27.029333-1.002667-3.168-1.76-4.373333-2.24-4.768-1.226667-1.056-5.418667-1.962667-19.744-2.858667a283.594667 283.594667 0 0 1-15.498666-1.237333c-27.701333-3.093333-49.088-12.768-66.069334-35.061333-25.749333-33.781333-22.901333-61.141333-3.808-104.234667 7.904-17.856 9.397333-23.317333 8.544-26.432-0.277333-1.034667-1.056-2.4-2.912-4.426667-7.125333-7.797333-25.525333-8.917333-52.384-0.672-12.373333 3.797333-25.301333 9.258667-37.130666 15.445334-9.12 4.768-16.714667 9.578667-18.837334 11.445333-19.178667 16.821333-60.981333 19.541333-90.986666 7.936-44.064-17.056-59.456-60.672-34.08-113.088z m505.834667 85.610667a32 32 0 1 1-63.253334-9.706667C873.92 403.733333 874.666667 393.92 874.666667 384c0-106.037333-85.962667-192-192-192-2.794667 0-5.578667 0.064-8.352 0.181333a32 32 0 1 1-2.730667-63.946666c3.690667-0.16 7.381333-0.234667 11.082667-0.234667 141.386667 0 256 114.613333 256 256 0 13.173333-1.002667 26.24-2.976 39.114667z m-104.288-14.976a32 32 0 1 1-63.744-5.717334A85.333333 85.333333 0 0 0 682.666667 309.333333a32 32 0 0 1 0-64c82.474667 0 149.333333 66.858667 149.333333 149.333334 0 4.512-0.202667 9.013333-0.597333 13.472z" fill="#515151" p-id="4296"></path></svg>
                        
                    </a>
                </li>
            
        </ol><ol class="menu" id="main-menu">
        
        
        
        <li >
            <a href='/archives/' >
                
                
                
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-archive" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <rect x="3" y="4" width="18" height="4" rx="2" />
  <path d="M5 8v10a2 2 0 0 0 2 2h10a2 2 0 0 0 2 -2v-10" />
  <line x1="10" y1="12" x2="14" y2="12" />
</svg>



                
                <span>Archives</span>
            </a>
        </li>
        
        
        <li >
            <a href='/search/' >
                
                
                
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-search" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="10" cy="10" r="7" />
  <line x1="21" y1="21" x2="15" y2="15" />
</svg>



                
                <span>Search</span>
            </a>
        </li>
        
        
        <li >
            <a href='/about' >
                
                
                
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-user" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="7" r="4" />
  <path d="M6 21v-2a4 4 0 0 1 4 -4h4a4 4 0 0 1 4 4v2" />
</svg>



                
                <span>About</span>
            </a>
        </li>
        
        <li class="menu-bottom-section">
            <ol class="menu">

                
                    <li id="dark-mode-toggle">
                        <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-toggle-left" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="8" cy="12" r="2" />
  <rect x="2" y="6" width="20" height="12" rx="6" />
</svg>



                        <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-toggle-right" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="16" cy="12" r="2" />
  <rect x="2" y="6" width="20" height="12" rx="6" />
</svg>



                        <span>Dark Mode</span>
                    </li>
                
            </ol>
        </li>
    </ol>
</aside>

    <aside class="sidebar right-sidebar sticky">
        
            
                
    <section class="widget archives">
        <div class="widget-icon">
            <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-hash" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <line x1="5" y1="9" x2="19" y2="9" />
  <line x1="5" y1="15" x2="19" y2="15" />
  <line x1="11" y1="4" x2="7" y2="20" />
  <line x1="17" y1="4" x2="13" y2="20" />
</svg>



        </div>
        <h2 class="widget-title section-title">Table of contents</h2>
        
        <div class="widget--toc">
            <nav id="TableOfContents">
  <ul>
    <li><a href="#pmem架构">PMem架构</a></li>
    <li><a href="#pmem运行模式">PMem运行模式</a></li>
    <li><a href="#pmem读写">PMem读写</a></li>
    <li><a href="#延时测试">延时测试</a></li>
    <li><a href="#访问粒度对带宽的影响">访问粒度对带宽的影响</a></li>
  </ul>

  <ul>
    <li><a href="#传统块设备文件系统-vs-持久内存文件系统">传统块设备文件系统 vs 持久内存文件系统</a></li>
    <li><a href="#文件系统的结构特征">文件系统的结构特征</a></li>
    <li><a href="#数据更新机制">数据更新机制</a></li>
    <li><a href="#nvm-dram-混合内存文件系统">NVM-DRAM 混合内存文件系统</a></li>
  </ul>

  <ul>
    <li><a href="#非关系型数据库">非关系型数据库</a></li>
    <li><a href="#k-v-store">K-V store</a></li>
  </ul>

  <ul>
    <li><a href="#树型索引">树型索引</a></li>
    <li><a href="#哈希索引结构">哈希索引结构</a>
      <ul>
        <li><a href="#布谷鸟散列">布谷鸟散列</a></li>
      </ul>
    </li>
  </ul>

  <ul>
    <li><a href="#数据的崩溃一致性问题">数据的崩溃一致性问题</a></li>
    <li><a href="#原子更新技术sfenceclflush">原子更新技术：sfence、clflush</a></li>
    <li><a href="#日志">日志</a></li>
    <li><a href="#写时拷贝">写时拷贝</a></li>
  </ul>
</nav>
        </div>
    </section>

            
        
            
                <section class="widget tagCloud">
    <div class="widget-icon">
        <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-tag" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <path d="M11 3L20 12a1.5 1.5 0 0 1 0 2L14 20a1.5 1.5 0 0 1 -2 0L3 11v-4a4 4 0 0 1 4 -4h4" />
  <circle cx="9" cy="9" r="2" />
</svg>



    </div>
    <h2 class="widget-title section-title">Tags</h2>

    <div class="tagCloud-tags">
        
            <a href="/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" class="font_size_2">
                操作系统
            </a>
        
            <a href="/tags/intel/" class="font_size_1">
                intel
            </a>
        
            <a href="/tags/%E8%BD%AF%E4%BB%B6/" class="font_size_1">
                软件
            </a>
        
    </div>
</section>
            
        
    </aside>


            <main class="main full-width">
    <article class="has-image main-article">
    <header class="article-header">
        <div class="article-image">
            <a href="/post/nvm_report/">
                
                    <img src="/post/dcpmm.jpg" loading="lazy" alt="Featured image of post NVM方向调研" />
                
            </a>
        </div>
    

    <div class="article-details">
    
    <header class="article-category">
        
            <a href="/categories/nvm/" >
                NVM
            </a>
        
    </header>
    

    <div class="article-title-wrapper">
        <h2 class="article-title">
            <a href="/post/nvm_report/">NVM方向调研</a>
        </h2>
    
        
        <h3 class="article-subtitle">
            英特尔傲腾技术具有开创性地将内存和存储融为一体。持久内存是一项变革性的内存技术，持久内存将经济实惠的更大容量与对数据持久性的支持巧妙的结合在一起。以创新技术提供独特的操作模式，可以满足您针对各种工作负载的需求。
        </h3>
        
    </div>

    
    
    
    
    <footer class="article-time">
        
            <div>
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-calendar-time" width="56" height="56" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <path d="M11.795 21h-6.795a2 2 0 0 1 -2 -2v-12a2 2 0 0 1 2 -2h12a2 2 0 0 1 2 2v4" />
  <circle cx="18" cy="18" r="4" />
  <path d="M15 3v4" />
  <path d="M7 3v4" />
  <path d="M3 11h16" />
  <path d="M18 16.496v1.504l1 1" />
</svg>
                <time class="article-time--published">2022 年 3 月 31 日</time>
            </div>
        

        
            <div>
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-clock" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="12" r="9" />
  <polyline points="12 7 12 12 15 15" />
</svg>



                <time class="article-time--reading">
                    2 minute read
                </time>
            </div>
        
    </footer>
    

    
</div>

</header>

    <section class="article-content">
    
    
    <h1 id="研究方向">研究方向
</h1><ul>
<li>文件系统</li>
<li>键值存储系统</li>
<li>索引结构</li>
<li>数据一致性</li>
<li>磨损均衡</li>
<li>动态图</li>
</ul>
<h1 id="傲腾pmem特性">傲腾PMem特性
</h1><h2 id="pmem架构">PMem架构
</h2><ol>
<li>每个 CPU 芯片有2个 iMC，每个 iMC 支持3个通道，所以每个 CPU 芯片支持6个傲腾DIMM。一台双 CPU 的服务器最大可装载 6TB (2 socket * 6 channel * 512GB/DIMM = 6TB)。</li>
<li>使用 ADR 域来掉电保护；CPU中的 iMC 中为每个傲腾 DIMM 维护着读/写挂起队列，WPQ 在ADR 域中，只要数据达到 WPQ 中，ADR域即可确保在掉电后 iMC 把数据刷回 DIMM；Cache中的数据无法保护，ADR域中的 WPQ 和 XPBuffer 中的数据可以被持久化。</li>
</ol>
<h2 id="pmem运行模式">PMem运行模式
</h2><ol>
<li><strong>内存模式</strong>：DCPMM为易失性，一个DCPMM和一个DRAM组合在同一个内存通道上，DRAM 相当于一个 L4 级缓存，缓存块为 64B， DCPMM被视为主存。</li>
<li><strong>直连模式</strong>： DCPMM提供持久性，可以使用交错和非交错配置；交错的DCPMM被视为一个整体空间，将数据等量分散存储到各个DIMM，交错大小为4KB，类似RAID 0；非交错的DCPMM将一个 DIMM的内存空间追加到另一个DIMM的后面。</li>
</ol>
<h2 id="pmem读写">PMem读写
</h2><ol>
<li>iMC 与傲腾 PMem 之间通过基于事物的双倍速率协议 (DDR-T) 以缓存行大小 (64B) 的粒度进行传输。</li>
<li>傲腾 PMem 内部的最小读写粒度为 256B，内部用一个小的写合并缓冲区 XPBuffer 来解决 DDR-T协议传输粒度和傲腾 PMem 的操作粒度不一致的问题。例如，64 B的数据写操作需要先从傲腾 PMem中将对应的256 B数据读入到 XPBuffer 中，然后在 XPBuffer 中更新请求的64 B数据，最后再将256 B数据写入到傲腾PMem存储介质中。这一操作会导致写放大，降低傲腾PMM的性能。</li>
</ol>
<h2 id="延时测试">延时测试
</h2><p>傲腾 PMem 内部的最小读写粒度为 256B，内部用一个小的写合并缓冲区 XPBuffer 来解决 DDR-T协议传输粒度和傲腾 PMem 的操作粒度不一致的问题。例如，64 B的数据写操作需要先从傲腾 PMem中将对应的256 B数据读入到 XPBuffer 中，然后在 XPBuffer 中更新请求的64 B数据，最后再将256 B数据写入到傲腾PMem存储介质中。这一操作会导致写放大，降低傲腾PMM的性能。</p>
<p><img src="/post/timetest1.png"
	
	
	
	loading="lazy"
	
		alt="延时测试"
	
	
></p>
<h2 id="访问粒度对带宽的影响">访问粒度对带宽的影响
</h2><ul>
<li>DRAM：访问粒度的大小对读写带宽没什么影响；</li>
<li>交错和非交错：访问粒度小于 256B时会造成较差的带宽，原因是 XPLine大小为 256B；</li>
<li>非交错：读写带宽较非交错提升 5.8x 和 5.6x (与交错的DIMM个数接近)，在 4KB 处带宽降低，接近交错大小，最大化 iMC 竞争；尽量避免以4KB的交错大小进行随机访问；</li>
</ul>
<p><img src="/post/bandwidth1.png"
	
	
	
	loading="lazy"
	
		alt="带宽测试"
	
	
></p>
<h1 id="文件系统">文件系统
</h1><h2 id="传统块设备文件系统-vs-持久内存文件系统">传统块设备文件系统 vs 持久内存文件系统
</h2><ul>
<li>基于块设备的文件系统：读写粒度通常为 512B 或 4KB，如文件系统需要修改块设备中的 8B 时，需要找到这 8B 所在的块号，将其所在的 4KB 块读取到内存中的 page cache中，再拷贝到应用缓冲区，在应用缓冲区中修改这 8B ，并将修改后的缓存页写回到块设备，是一个“读取-修改-写回”的过程，存在双份拷贝花销的问题、写放大问题、块设备访问速度慢导致大量的访问操作会带来 I/O 阻塞问题。
<ul>
<li><strong>读缓存</strong>：文件访问具有时间局部性，从块设备读取了一个文件的数据后，可以让它在内存中保存一段时间，命中时可直接访问；</li>
<li><strong>写缓冲区和写合并</strong>：文件访问具有空间局部性，文件在高速缓存页中修改之后，不马上持久化，若后续再次请求修改相同的块时，可直接修改。</li>
</ul>
</li>
<li>基于持久内存的文件系统：NVM 设备直接连接在 DDR 内存通道，移除了页高速缓存和块设备的写入缓冲区和写入合并；具有可按字节寻址的特性，数据直接在文件系统和应用缓冲区之间通过 Load/Store 访存，无需以整个块粒度读写；</li>
<li>持久内存文件系统的优点
<ul>
<li>访问文件数据不需要经过传统面向块设备的 I/O 软件层次，文件请求到内存级就直接返回;</li>
<li>访问文件数据不需要多次拷贝，不需要经过 VFS 中的高速缓存，因为PM是直接装在内存总线上，直接在内存与用户进程缓冲区之间直接拷贝数据；</li>
<li>访问NVM通常不会引起进程阻塞挂起。</li>
</ul>
</li>
</ul>
<p><img src="/post/pm1.png"
	
	
	
	loading="lazy"
	
		alt="持久内存文件系统架构"
	
	
></p>
<h2 id="文件系统的结构特征">文件系统的结构特征
</h2><ul>
<li>索引结构：树形索引 vs 哈希索引 vs 跳表</li>
<li>内存架构：纯NVM vs DRAM-NVM混合内存</li>
<li>数据更新机制：日志型更新 vs 写时复制</li>
<li>是否支持 MMap：是 vs 否</li>
<li>访问均衡性：弱 vs 强</li>
<li>一致性层级：元数据一致性 vs 数据一致性 vs 版本一致性</li>
</ul>
<p><img src="/post/fs.png"
	
	
	
	loading="lazy"
	
		alt="现有的研究工作"
	
	
></p>
<h2 id="数据更新机制">数据更新机制
</h2><ul>
<li><strong>日志</strong>：一种原地更新的方式，是指新数据在旧数据所在的位置上进行更新，新写入的数据将覆盖原有数据，对于可能存在的不完整写问题，一般采取记录日志 (Journaling) 的方式对被修改前的数据和被修改后的数据进行记录，更新完全成功后再丢弃日志。</li>
<li><strong>写时复制</strong>：一种异地更新方式，写时复制是指当进行数据更新时，先将原有数据原原本本地复制一份，然后在复制出的副本上进行数据修改，数据修改完成后再将数据原本删除，若修改失败，则将数据恢复到原本状态，这样就即可以完成数据更新，又保证了数据更新的一致性。</li>
</ul>
<h2 id="nvm-dram-混合内存文件系统">NVM-DRAM 混合内存文件系统
</h2><ul>
<li>DRAM 和 NVM 采用平行架构，DRAM 和 NVM 同时作为系统主存连接在内存控制器上，俩者采用统一编址的方式；</li>
<li>关键的变化是如何确定 DRAM 和 NVM 各自存放程序的哪些数据，当系统发生异常时DRAM掉电易失，而 NVM 中的数据在 DRAM 中的数据已然丢失的情况下，如何维护数据一致性；</li>
<li>对应为 Intel 傲腾持久内存的 App-Direct Mode，系统可用的总内存空间为DRAM和NVM容量之和。被更多的研究采用。</li>
</ul>
<p><img src="/post/h1.png"
	
	
	
	loading="lazy"
	
		alt="混合内存架构"
	
	
></p>
<h1 id="键值存储系统">键值存储系统
</h1><h2 id="非关系型数据库">非关系型数据库
</h2><p>主要可以分为四种类型：</p>
<ul>
<li><strong>键值对存储</strong> (Key-Value Store)：其基本结构就是一个 Key-Value 的映射关系集合；</li>
<li><strong>文档存储</strong> (Document Store)：如MongoDB；</li>
<li><strong>列数据库</strong> (Column-oriented Store)：将每一列分别单独存放数据。与基于行的传统关系型数据库的区别在于：以牺牲存储空间和更多的索引文件为代价使得查找速度得到提升，主要适用于批量数据处理和即时查询，而数据以行相关的存储体系架构，主要适合于大规模的数据处理和联机事务型数据处理；如Cassandra、HBase；</li>
<li><strong>图数据库</strong> (Graph Database)：又分为静态图和动态图。适用于被存储的数据之间具有较为紧密的联系，图形数据库主要由两部分组成，节点和连接边，节点表示实体本身，连接边表示实体之间的关系。如静态图数据库Neo4J、动态图数据库Stinger。</li>
</ul>
<h2 id="k-v-store">K-V store
</h2><p>键值对存储系统主要采用的数据结构：LSM树、B+树、哈希表、跳表</p>
<ul>
<li><strong>LSM树</strong>：LSM 树多用于 HDD 或 SSD 的键值对存储系统，在内存中将随机写请求聚集并顺序写到外存中，适应HDD 或 SSD的顺序写性能远远高于随机写性能的特性；LSM 树主要应用于查询频率远远低于写入频率的情况，能降低索引的写入开销。</li>
<li><strong>哈希表</strong>：主要被用在基于内存的场景中，利用了哈希表常数级别的点操作时间复杂度，包括Add、Get、Update、Delete等操作。</li>
</ul>
<h1 id="索引结构">索引结构
</h1><h2 id="树型索引">树型索引
</h2><p>一般B+树、基数树，为有序索引数据结构，范围查询的性能最好，但需要额外的开销来维护有序性。Add、Get、Update、Delete、Scan等操作的时间复杂度都为O(logN)。</p>
<p><img src="/post/tree.png"
	
	
	
	loading="lazy"
	
		alt="现有研究工作"
	
	
></p>
<h2 id="哈希索引结构">哈希索引结构
</h2><p>哈希表完全不维护数据结构中的有序性，一般而言额外开销最小，范围查询时需要遍历所有的键值对，效率很低。不过Add、Get、Update、Delete等点操作类型的时间复杂度都是O(1)，性能优于树形索引结构。</p>
<ul>
<li><strong>静态哈希</strong>：适合数据集大小相对稳定的场景，在插入频繁的场景下，数据的波动较大，静态哈希要重建哈希索引进行扩容，导致大量的NVM写操作，造成性能的抖动和下降，且在并发时要对扩容的哈希索引加锁，导致索引的访问被阻塞。</li>
<li><strong>动态哈希</strong>：包括可扩展哈希、线性哈希；动态哈希通过桶分裂来增量式扩容，扩容过程不需要重建整个哈希索引，而且不需要加锁，平衡了可扩展性和性能。</li>
</ul>
<h3 id="布谷鸟散列">布谷鸟散列
</h3><p>布谷鸟散列：使用俩个哈希函数分别计算 key对应的位置：</p>
<ol>
<li>若两个位置均为空，任选一个插入；</li>
<li>若两个位置中一个为空，插入到空的位置；</li>
<li>若两个位置均非空，则随机踢出一个位置上的 keyx，被踢出的 keyx 再执行该算法找其另一个位置，循环直到插入成功；</li>
<li>如果被踢出的次数达到一定的阈值，则认为hash表已满，并进行重新哈希 rehashing。</li>
</ol>
<p><img src="/post/hash.png"
	
	
	
	loading="lazy"
	
		alt="现有工作研究"
	
	
></p>
<h1 id="数据一致性">数据一致性
</h1><h2 id="数据的崩溃一致性问题">数据的崩溃一致性问题
</h2><ul>
<li><strong>写粒度问题</strong>：CPU对SSD原子写的粒度为闪存页大小4KB ，对HDD原子写的粒度为扇区大小512B，可以保证一条日志的追加更新是原子性的。而CPU对NVM的原子写粒度只有8B，面临修改持久性数据的过程中发生断电导致数据不一致的问题。</li>
<li><strong>缓存问题</strong>：传统DRAM和Cache都是易失的，系统在DRAM和Cache之间采用写回法和写分配法的策略不会产生断电恢复的问题。而NVM作为全部内存时，CPU先写入Cache中，没有写入NVM中。这样指令运行结束之后，我们无法判断数据何时才会真正被持久化存储，在断电后无法判断数据出于何种状态。</li>
<li><strong>CPU重排序问题</strong>：对于多周期流水线CPU，在一个基本时钟周期内同时从指令Cache中读出多条指令，同时对多条指令进行译码。当指令没有数据相关性时且有空闲运算部件时就会被执行，不能保证各个语句执行的先后顺序和输入代码中的顺序一致。</li>
</ul>
<h2 id="原子更新技术sfenceclflush">原子更新技术：sfence、clflush
</h2><p><strong>内存屏障</strong>：CPU 采用乱序调度来增加性能，但 NVM 的写入要保证顺序性否则会导致崩溃一致性的问题，内存屏障的方式如 sfence 指令，可以保证 cache line 刷回NVM 的顺序。但加入 sfence 等内存屏障指令降低 CPU 流水线效率会降低处理器性能。</p>
<p><strong>缓存行刷新</strong>：x86 提供了 clflush、clflushopt 和 clwb 等指令可以让数据在每次对NVM的写入操作之后从 cache line 强制写回到 NVM。但这些指令减少了Cache作为高速缓存的作用，降低了处理器性能。clwb 指令后跟着 sfence 指令为一次持久化操作。</p>
<p><img src="/post/flush1.png"
	
	
	
	loading="lazy"
	
		alt="fl"
	
	
></p>
<p><img src="/post/flush2.png"
	
	
	
	loading="lazy"
	
		alt="fl"
	
	
></p>
<h2 id="日志">日志
</h2><p>redo日志、undo日志：或叫做写前日志，是一种原地更新设计。</p>
<ul>
<li>undo日志：原始值被修改之前，将原始值存储到undo日志中，如果修改出现异常，可以对undo日志进行回滚；</li>
<li>redo日志：将数据位置和此位置上即将被写入的新数据保存在日志中，日志提交之后用户进行真正的修改，在恢复的时候根据这个日志把数据重写到记录的位置上。</li>
</ul>
<p>redo 日志一旦提交，就认为已成功持久化，无论修改是否已经写到原位置上；
undo 日志使用时，数据修改的持久化取决于日志是否被标记为无效。只有真实的修改被写到原位置上，用户再将 undo 日志标记为无效，才能保证完成持久化。</p>
<h2 id="写时拷贝">写时拷贝
</h2><p>写时拷贝：修改数据时，先对原数据进行一次拷贝，在拷贝出来的数据副本上进行修改。此后，写时拷贝通过继续修改指向原数据的指针，使其指向新数据，让副本中的数据修改生效。写时拷贝经常被用在树形结构中。</p>

</section>


    <footer class="article-footer">
    

    </footer>


    
        <link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/katex@0.16.9/dist/katex.min.css"integrity="sha384-n8MVd4RsNIU0tAv4ct0nTaAbDJwPJzDEaqSD1odI&#43;WdtXRGWt2kTvGFasHpSy3SV"crossorigin="anonymous"
            ><script 
                src="https://cdn.jsdelivr.net/npm/katex@0.16.9/dist/katex.min.js"integrity="sha384-XjKyOOlGwcjNTAIQHIpgOno0Hl1YQqzUOEleOLALmuqehneUG&#43;vnGctmUb0ZY0l8"crossorigin="anonymous"
                defer
                >
            </script><script 
                src="https://cdn.jsdelivr.net/npm/katex@0.16.9/dist/contrib/auto-render.min.js"integrity="sha384-&#43;VBxd3r6XgURycqtZ117nYw44OOcIax56Z4dCRWbxyPt0Koah1uHoK0o4&#43;/RRE05"crossorigin="anonymous"
                defer
                >
            </script><script>
    window.addEventListener("DOMContentLoaded", () => {
        renderMathInElement(document.body, {
            delimiters: [
                { left: "$$", right: "$$", display: true },
                { left: "$", right: "$", display: false },
                { left: "\\(", right: "\\)", display: false },
                { left: "\\[", right: "\\]", display: true }
            ],
            ignoredClasses: ["gist"]
        });})
</script>
    
</article>

    

    

     
    
        
    

    <footer class="site-footer">
    <section class="copyright">
        &copy; 
        
            2022 - 
        
        2024 ydsungan 的博客
    </section>
    
    <section class="powerby">
        Built with <a href="https://gohugo.io/" target="_blank" rel="noopener">Hugo</a> <br />
        Theme <b><a href="https://github.com/CaiJimmy/hugo-theme-stack" target="_blank" rel="noopener" data-version="3.27.0">Stack</a></b> designed by <a href="https://jimmycai.com" target="_blank" rel="noopener">Jimmy</a>
    </section>
</footer>


    
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    
    <div class="pswp__bg"></div>

    
    <div class="pswp__scroll-wrap">

        
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                
                
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div><script 
                src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js"integrity="sha256-ePwmChbbvXbsO02lbM3HoHbSHTHFAeChekF1xKJdleo="crossorigin="anonymous"
                defer
                >
            </script><script 
                src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js"integrity="sha256-UKkzOn/w1mBxRmLLGrSeyB4e1xbrp4xylgAWb3M42pU="crossorigin="anonymous"
                defer
                >
            </script><link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.min.css"crossorigin="anonymous"
            ><link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.css"crossorigin="anonymous"
            >

            </main>
        </div>
        <script 
                src="https://cdn.jsdelivr.net/npm/node-vibrant@3.1.6/dist/vibrant.min.js"integrity="sha256-awcR2jno4kI5X0zL8ex0vi2z&#43;KMkF24hUW8WePSA9HM="crossorigin="anonymous"
                
                >
            </script><script type="text/javascript" src="/ts/main.js" defer></script>
<script>
    (function () {
        const customFont = document.createElement('link');
        customFont.href = "https://fonts.googleapis.com/css2?family=Lato:wght@300;400;700&display=swap";

        customFont.type = "text/css";
        customFont.rel = "stylesheet";

        document.head.appendChild(customFont);
    }());
</script>

    </body>
</html>
